package previous.Test_0226;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Solution {
    //爬楼梯
    public int waysToStep(int n) {
          int[] dp=new int[n+1];
          if(n==1 || n==2){
              return n;
          }
          if(n==3){
              return 4;
          }
          //取模
        int MOD=(int)1e9+7;
          dp[1]=1;
          dp[2]=2;
          dp[3]=4;
        for (int i = 4; i <=n ; i++) {
            //这一步是为什么
            dp[i]=((dp[i-1]+dp[i-2])%MOD+dp[i-3])%MOD;
        }
        return dp[n];
    }
    //使用最小费用爬楼梯
    //dp[i]=dp[i]+前面的最小花费
    public int minCostClimbingStairs(int[] cost) {
          int n=cost.length;
          if(n==1 || n==2){
              return Math.min(cost[0],cost[1]);
          }
          int[] dp=new int[n];
        for (int i = 2; i <n; i++) {
            dp[i]=Math.min(cost[i-1]+dp[i-1],cost[i-2]+dp[i-2]) ;
        }
        return dp[n];
    }

    }


